package DoExercise.HSP_ZCY.A014_贪心_总是当前的全局最优解;

import java.util.PriorityQueue;

/**
 * 一块金条切成两半，是需要花费和长度数值一样的铜板的。
 * 比如长度为20的金条，不管怎么切，都要花费20个铜板。
 * 长度是60的金条，假如先切30 30，再切 20 10 总共就花费90；长度是60的金条，假如先切50 10，再切 20 30 总共就花费110；
 * 给定一个金条长度100，切分为{20，30，50}，请问怎样的切分的顺序才能最省铜板?
 *
 * 其实就是哈夫曼树
 */
public class Code03_切金条最少的花费
{
    public static void main(String[] args)
    {
        int testTime = 100000;
        int maxSize = 6;
        int maxValue = 1000;
        for (int i = 0; i < testTime; i++)
        {
            int[] arr = generateRandomArray(maxSize, maxValue);
            if (lessMoney1(arr) != lessMoney2(arr))
            {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
    
    public static int lessMoney1(int[] arr)
    {
        if (arr == null || arr.length == 0)
        {
            return 0;
        }
        return process(arr, 0);
    }
    
    public static int process(int[] arr, int pre)
    {
        if (arr.length == 1)
        {
            return pre;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++)
        {
            for (int j = i + 1; j < arr.length; j++)
            {
                ans = Math.min(ans, process(copyAndMergeTwo(arr, i, j), pre + arr[i] + arr[j]));
            }
        }
        return ans;
    }
    
    public static int[] copyAndMergeTwo(int[] arr, int i, int j)
    {
        int[] ans = new int[arr.length - 1];
        int ansi = 0;
        for (int arri = 0; arri < arr.length; arri++)
        {
            if (arri != i && arri != j)
            {
                ans[ansi++] = arr[arri];
            }
        }
        ans[ansi] = arr[i] + arr[j];
        return ans;
    }

    /**
     *
     * 贪心策略，每次都选择消耗金币最少的切
     *
     * @param arr
     * @return
     */
    public static int lessMoney2(int[] arr)
    {
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++)
        {
            pQ.add(arr[i]);
        }
        int sum = 0;
        while (pQ.size() > 1)
        {
            int cur = pQ.poll() + pQ.poll();
            sum += cur;
            pQ.add(cur);
        }
        return sum;
    }
    
    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue)
    {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++)
        {
            arr[i] = (int) (Math.random() * (maxValue + 1));
        }
        return arr;
    }
}
